In present day multilevel and complex memory systems, access time to a memory upon the request by a CPU for instructions or data can engender considerable delays. A memory hierarchy is needed which is arranged according to the order in which the CPU accesses data from different memories in the hierarchy, as shown in FIG. 1. Referring to FIG. 1, the CPU accesses memories in the order of a register 10, a cache system 11, a main memory 12, a disk 13, and a tape 14. Here, the register 10 having the fastest access time is referred to as the highest hierarchical level and the tape 14 having the slowest access time is referred to as the lowest hierarchical level.
Among the above memories, the cache system 11 is accessed prior to the main memory 12, and therefore the structure and controlling method of the cache system may significantly impact the execution speed and power consumption of a CPU. The cache system 11 is designed and controlled based on the principle of locality.
The locality is categorized into spatial locality and temporal locality. The spatial locality refers to the tendency for adjacent or nearby memory locations to be referenced close together in time. The temporal locality is the likelihood that data retrieved once will be retrieved again soon.
Cache systems exploit the temporal locality by retaining recently referenced data, and the spatial locality by fetching multiple words as a cache block whenever a miss occurs. These two approaches for optimizing each type of locality contradict each other when cache capacity is fixed. Typically, the increment in the block size is inversely proportional to the number of cache blocks. For this reason, as the size of a block increases, more data adjacent to the accessed memory address are copied in the cache system. In this case, referenced data resides a shorter amount of time in the cache system because of the reduced number of cache blocks. Thus, if the storage capacity of the cache system is fixed at a predetermined level, as the size of a block increases, the cache system has a higher spatial locality but a lower temporal locality. Conversely, as the size of a block decreases, the cache system has a lower spatial locality but a higher temporal locality.
To reduce the above conflicts as much as possible, a cache system has been proposed to include two cache memories, which are separately controlled. According to a conventional cache control method of the cache system, complex mechanisms were used to exploit two localities, e.g., methods of using locality prediction table, compiler, locality detection unit, prefetching, and so forth. These conventional cache control methods have problems in that they are complex in design and have high hardware cost.